#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN=1050;
int d[MAXN][MAXN];
//O(nlogn)预处理
//预处理维护了一个d数组，d[i][j]表示从i开始，长度为2^j的一段元素中的最小值
void RMQ_init(const vector<int>& A){
	int n=A.size();
	for(int i=0;i<n;i++){
		d[i][0]=A[i];
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=0;i+(1<<j)-1<n;i++){
			d[i][j]=min(d[i][j-1],d[i+(1<<j)][j-1]);
		}
	}
}
//O(1)查询
//
int RMQ(int L,int R){
	int k=0;
	while((1<<(k+1))<=R-L+1){
		k++;
	}
	//因为无法保证L和R就刚好相差2^j，所以等于要取两个区间的最小值
	//令k满足2^k<=R-L+1 所以k可以将查询区间分为两个(长度均为2^k,可重叠)
	return min(d[L][k],d[R-(1<<k)+1][k]);
}
int main(void){
	//省略
	return 0;
}
